leetcode 39. 组合总和(python) |
您所在的位置:网站首页 › 组合总数 两个目标值 › leetcode 39. 组合总和(python) |
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。 说明: 所有数字(包括 target)都是正整数。解集不能包含重复的组合。 示例 1: 输入: candidates = [2,3,6,7], target = 7,所求解集为:[ [7], [2,2,3]]示例 2: 输入: candidates = [2,3,5], target = 8,所求解集为:[ [2,2,2,2], [2,3,3], [3,5]] class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: self.res = [] if len(candidates) target: # 剪枝操作,当当前数值大于目标值,则后续无需遍历 return if num < last: # 剪枝操作:若当前数值小于当前sublist的最后一个元素,则继续遍历,防止出现重复解决方案,如[2,2,3],[3,2,2] continue self.dfs(candidates,sublist+[num],target-num,num)参考: https://blog.csdn.net/weixin_40546602/article/details/88357837 递归函数 dfs(candidates,sublist,target,last),其中sublist记录当前满足条件的子数组,last为当前子数组的最后一个元素。 剪枝操作1:目标值小于元素数组的最小元素,则无需继续遍历 剪枝操作2:当前元素大于目标值,则后续元素一定大于目标值(数组已排序),不会满足条件,无需继续遍历 剪枝操作3:若当前数值小于当前sublist的最后一个元素,则继续遍历,防止出现重复解决方案,如[2,2,3],[3,2,2] |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |